package com.lans.binary;

/**
 * @author: lans
 * @date: 2025/3/1
 * @name: 刘宇
 */
public class MinQueue <T extends Comparable<T>> {

    private T[] items;

    private int N;

    public MinQueue(int capacity){
        items = (T[])new Comparable[capacity];
        N=0;
    }

    //true-> i<j
    public boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }

    public void exch(int i,int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    public T delMin(){
        //找到最小值
        T min = items[1];
        //交换根节点和N处节点的位置
        exch(1,N);
        items[N]=null;
        N--;
        sink(1);
        return min;
    }

    public void insert(T t){
        items[++N] = t;
        swim(N);
    }

    //上浮算法
    public void swim(int k){
        while(k>1){
            if(less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }

    //下沉算法
    public void sink(int k){
        //如果没有子节点就不在继续下沉
        while(2*k<=N){
            //找出节点中比较小的值
            int min  = 2*k;
            if(2*k+1<=N&&less(2*k+1,2*k)){
                min = 2*k+1;
            }
            if(less(k,min)){
                break;
            }
            exch(k,min);
            k=min;
        }
    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N==0;
    }

    public static void main(String[] args) {
        String[] strings = {"s","t","r","x","n","h","p"};
        MinQueue<String> minQueue = new MinQueue<>(15);
        for(String s:strings){
            minQueue.insert(s);
        }
        String remove;
        while(!minQueue.isEmpty()){
            remove = minQueue.delMin();
            System.out.println(remove);
        }
    }
}